public class test {
    //leetcode 121.买卖股票的最佳时机
    class Solution {
        public int maxProfit(int[] prices) {
            //创建min和max
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            //返回最大的num(max - min)
            int num = Integer.MIN_VALUE;
            for(int i = 0;i < prices.length;i++){
                min = Math.min(prices[i],min);
                max = Math.max(prices[i],max);
                //当购买新股票时,将之前的最大出售价清空
                if(min == prices[i]){
                    max = 0;
                }
                num = Math.max(max - min,num);
            }
            return num > 0 ? num : 0;
        }
    }
    //leetcode 309.买卖股票的最佳时机含冷冻期
    class Solution {
        public int maxProfit(int[] prices) {
            // 1. 创建dp[]表
            int n = prices.length;
            if(n == 1){
                return 0;
            }
            //dp[i][0]代表状态"买入"
            //dp[i][1]代表状态"卖出(可交易)"
            //dp[i][2]代表状态"冷冻期"
            int[][] dp = new int[n+1][3];
            // 2. 初始化
            dp[1][0] = -prices[0];
            // 3. 填表
            for(int i = 2;i <= n;i++){
                //买
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - prices[i-1]);
                //可交易
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
                //冷冻期(卖)
                dp[i][2] = dp[i-1][0] + prices[i-1];
            }
            // 4. 返回值
            return Math.max(dp[n][1],dp[n][2]);
        }
    }
    //leetcode 714.买卖股票的最佳时期含手续费
    class Solution {
        public int maxProfit(int[] prices, int fee) {
            // 1. 创建dp[]表
            int n = prices.length;
            //[i][0]代表买入,[i][1]代表卖出
            int[][] dp = new int[n][2];
            // 2. 初始化
            dp[0][0] = -prices[0];
            // 3. 填表
            for(int i = 1;i < n;i++){
                //买
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - prices[i]);
                //卖
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i] - fee);
            }
            // 4. 返回值
            return Math.max(dp[n-1][0],dp[n-1][1]);
        }
    }
    //leetcode 122.买卖股票的最佳时机Ⅱ
    class Solution {
        public int maxProfit(int[] prices) {
            // 1. 创建dp[]表
            int n = prices.length;
            //[i][0]代表买入
            //[i][1]代表出售
            int[][] dp = new int[n][2];
            // 2. 初始化
            dp[0][0] = -prices[0];
            // 3. 填表
            for(int i = 1;i < n;i++){
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - prices[i]);
                dp[i][1] = Math.max(dp[i-1][0] + prices[i],dp[i-1][1]);
            }
            // 4. 返回值
            return Math.max(dp[n-1][0],dp[n-1][1]);
        }
    }
    //leetcode 123.买卖股票的最佳时机Ⅲ
    class Solution {
        public int maxProfit(int[] prices) {
            // 1. 创建dp[]表
            // 最多完成两笔交易!
            int n = prices.length;
            // f[i][j] 代表第i天在[买入状态下]的最大利润,此时的交易次数为j
            int[][] f = new int[n][3];
            // g[i][j] 代表第i天在[卖出状态下]的最大利润,此时的交易次数为j
            int[][] g = new int[n][3];
            // 2. 初始化
            f[0][0] = -prices[0];
            // 防止使用INT_MIN时,后续状态转移方程报错
            f[0][1] = -0x3f3f3f3f;
            f[0][2] = -0x3f3f3f3f;
            g[0][1] = -0x3f3f3f3f;
            g[0][2] = -0x3f3f3f3f;
            // 3. 填表
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < 3; j++) {
                    f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                    g[i][j] = g[i - 1][j];
                    if (j > 0) {
                        g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                    }
                }
            }
            // 4. 返回值
            int max = 0;
            for (int i = 0; i < 3; i++) {
                max = Math.max(g[n - 1][i], max);
            }
            return max;
        }
    }
    //leetcode 188.买卖股票的最佳时机Ⅳ
    class Solution {
        public int maxProfit(int k, int[] prices) {
            // 1. 创建dp[]表
            int n = prices.length;
            int[][] f = new int[n][k+1];
            int[][] g = new int[n][k+1];
            // 2. 初始化
            for(int i = 0;i < k+1;i++){
                f[0][i] = -0x3f3f3f3f;
                g[0][i] = -0x3f3f3f3f;
            }
            f[0][0] = -prices[0];
            g[0][0] = 0;
            // 3. 填表
            for(int i = 1;i < n;i++){
                for(int j = 0;j < k + 1;j++){
                    f[i][j] = Math.max(f[i-1][j],g[i-1][j] - prices[i]);
                    g[i][j] = g[i-1][j];
                    if(j > 0){
                        g[i][j] = Math.max(g[i][j],f[i-1][j-1] + prices[i]);
                    }
                }
            }
            // 4. 返回值
            int max = 0;
            for(int i = 0;i < k + 1;i++){
                max = Math.max(g[n-1][i],max);
            }
            return max;
        }
    }
}
